package net.tp.algo.knapsack;

/**
 *
 * <p>Unbounded Knapsack Problem.</p>
 * <p>Input: n types of items, each with size $s_i$ and value $v_i$. Knapsack capacity $C$. $s_i$ and $C$ are integer.</p>
 *
 * <p>Goal: pack items into knapsack, maximize value. It's OK to use multiple instances of an item.</p>
 *
 * @author Trung Phan
 */
public class UnboundedKnapsack {

    public static int[] find(int[] sizes, double[] values, int capacity) {

        int N = sizes.length;

        double[] M = new double[capacity+1];
        int[] traces = new int[capacity+1];

        for (int c = 1; c <= capacity; c++) {
            for (int i = 0; i < N; i++) {
                if (sizes[i] <= c && M[c] < values[i] + M[c - sizes[i]]) {
                    M[c] = values[i] + M[c - sizes[i]];
                    traces[c] = i;
                }
            }
        }

        int[] result = new int[N];
        for (int c = capacity; c > 0; c -= sizes[traces[c]]) {
            result[traces[c]]++;
        }

        return result;
    }

}
